package puzzle.projecteuler.p100;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;

public class Problem026 {

	private static BufferedReader reader = new BufferedReader(
			new InputStreamReader(System.in));
	private static ArrayList<BigInteger> remainders = new ArrayList<BigInteger>();
	private static ArrayList<BigInteger> quotients = new ArrayList<BigInteger>();

	/**
	 * @param args
	 */
	public static void main(String[] args) {
	
		BigInteger numerator = BigInteger.ONE;
		BigInteger denominator = null;
		
		int len = 0;
		int d = 0;
		for (int i = 1; i < 1000; i ++) {
			denominator = BigInteger.valueOf(i);
			String s = number(numerator, denominator);
			if (s.indexOf(")")>-1 && s.indexOf("(")>-1) {
				int l = s.indexOf(")")-s.indexOf("(")-1;
				if (l > len) {
					len = l;
					d = i;
				}
			}
			remainders.clear();
			quotients.clear();
		}

		System.out.print(d);
	}
	
	private static String number(BigInteger numerator, BigInteger denominator) {
		
		BigInteger[] ret = numerator.divideAndRemainder(denominator);
		quotients.add(ret[0]);
		remainders.add(ret[1]);

		int repeatingStart = -1;

		// Exit loop if repeating part is found or divided without leaving a remainder
		while (ret[1].compareTo(BigInteger.ZERO) != 0) {
			ret = ret[1].multiply(BigInteger.TEN).divideAndRemainder(
					denominator);
			quotients.add(ret[0]);
			repeatingStart = getIndexOfRepeating(ret[1]);
			if (repeatingStart != -1)
				break;
			remainders.add(ret[1]);
		}

		// Print the result
		String s = (quotients.get(0).toString());
		if (quotients.size() > 1)
			s += '.';

		for (int i = 1; i < quotients.size(); i++) {
			if (i - 1 == repeatingStart)
				s += '(';
			s += quotients.get(i);
		}
		if (repeatingStart != -1)
			s += ')';
		
		return s;
	}

	/**
	 * Check the starting index of repeating decimal part
	 * @param rem
	 * @return
	 */
	private static int getIndexOfRepeating(BigInteger rem) {
		for (int j = 0; j < remainders.size(); j++) {
			if (rem.compareTo(remainders.get(j)) == 0)
				return j;
		}
		return -1;
	}

	/**
	 * Accept an valid integer from user's input
	 * @param msg The prompt message showed to user
	 * @return
	 */
	public static BigInteger acceptInteger(String msg) {
		BigInteger ret = null;
		boolean valid = false;
		while (!valid) {
			try {
				System.out.print(msg);
				String numeratorStr = null;
				try {
					numeratorStr = reader.readLine();
				} catch (IOException e) {
					// Ignore It should not occurs
					System.exit(1);
				}
				ret = new BigInteger(numeratorStr);
				valid = ret.compareTo(BigInteger.ZERO) == 1;
			} catch (NumberFormatException e) {
				// Do nothing
			}

			if (!valid)
				System.out.print("Your input is invalid, pls input again.");
		}

		return ret;
	}
}
